\documentclass[oneside]{ctexbook}
\usepackage{geometry}
\usepackage{pgfplots}
\usepackage{amsmath,amsthm}
\usepackage{graphicx}
\usepackage{tikz}
\usepackage{float}
\usepackage{ctex}
\usepackage{xeCJK}
\usepackage{bookmark}
\usepackage{cite}
\usepackage{subfigure}
\usepackage[linesnumbered,ruled,lined]{algorithm2e}
\newtheorem{Definition}{\hspace{2em}定义}
\newtheorem{lemma}{\hspace{2em}引理}
\newtheorem{Prop}{\hspace{2em}命题}
\newtheorem{thm}{\hspace{2em}定理}[section]
\newtheorem{corollary}{\hspace{2em}推论}[section]
\newenvironment{Proof}{{\noindent 证明:}\quad}{\hfill \par}


\newcommand\cnkeywords[1]{ {\heiti\zihao{-4}\cnkeywordsname: }#1}
\newcommand\cnkeywordsname{关键词}
\newcommand\cnabstractname{摘要}
\renewcommand{\contentsname}{目\qquad 录}
\newenvironment{cnabstract}{%
    \newpage
    \chapter[\cnabstractname]{\ziju{2}{\cnabstractname}}
    \songti\zihao{-4}
    }
    {\par}

\title{煤堆分层的网格处理}
\author{李博}
\date{\today}

\tikzset{math3d/.style={x={(-0.53cm,-0.353cm)},z={(0cm,1cm)},y={(1cm,0cm)}}}
\begin{document}
\maketitle
\pdfbookmark{目录}{toc}
\tableofcontents
\let\cleardoublepage\clearpage
\begin{cnabstract}
本文介绍煤堆分层的一种网格算法。该算法主要讨论了两个二维流形的交，二维带边（高亏格）流形的剖分和网格操作。在三维空间下的二维流形的求交主要涉及初等几何知识，
二维带边（高亏格）流形的剖分主要设计拓扑几何知识，网格操作涉及网格数据结构。该算法主要包含曲面网格求交，多边形区域网格剖分，环带区域网格剖分，多边界区域网格剖分，网格沿曲线切割。这些算法各自独立可重复使用，也可以组合为其他算法。比如，对两个曲面求交的到曲线，曲面沿曲线重新剖分网格，重建后的网格沿曲线切割，切割后的曲面重新粘连即可得到类似blender的bool运算效果。
\end{cnabstract}
\cnkeywords{网格算法}

\chapter{问题和背景}
\section{正文}
煤堆分层是对煤堆按高度进行分区。一般先对煤堆进行采样得到点云数据，然后对数据进行分区。
\begin{figure}[H]
\begin{center}
\begin{tikzpicture}
 \begin{axis}[width=11cm, height=7cm, tick align=outside]
   \addplot[draw=blue] coordinates {(-1,-1) (-0.5,-0.25) (0,0) (0.5,-0.25) (1,-1)}node{煤堆};
   \addplot[draw=blue,dashed] coordinates {(-1.2,-0.9) (1.2,-0.9)}node{分层高度};
 \end{axis}

\end{tikzpicture}
\caption{煤堆分层示意图}
\end{center}
\end{figure}
\chapter{算法}
\section{正文}
如果仅仅是解决煤堆分层方法有很多，本文方法的优势是可以处理更一般的问题和产生众多可以重复使用的算法，还可以组合得到想要的其他算法。

本算法是针对网格的算法，也就是将点云数据重建曲面后的网格。

那么煤堆分层的网格处理分为三步：
\begin{itemize}
    \item [1:]
    曲面的求交。
    \item [2:]
    曲面沿曲线重建网格。
    \item [3:]
    曲面沿曲线切割。

\end{itemize}

这样的处理能够得到一批能够重复使用的算法，还可以得到类似blender等三维软件的bool运算。
如果想要得到类似bool的效果，那么流程大概分为以下几步:

\begin{itemize}
    \item [1:]
    曲面的求交。
    \item [2:]
    曲面沿曲线重建网格。
    \item [3:]
    曲面沿曲线切割。
    \item [4:]
    曲面沿某条边界进行缝补合并。

\end{itemize}


步骤1,步骤3,步骤4逻辑较为简单，困难部分在c/c++编程实现上\cite{c++}。
步骤2包含了一系列理论问题。

步骤2的核心问题是求给定$n$条闭合曲线的网格剖分。

对于给定一条闭合曲线的网格剖分，也就是对$n$边形进行网格剖分。


对于给定$n$条闭合曲线的网格剖分，可以通过以下手法降为$n-1$条闭合曲线的网格剖分：
取出一条闭曲线$c$,对剩下的$n-1$闭曲线进行网格剖分得到$M_{n-1}$。那么$c$落在$M_{n-1}$上或者$M_{n-1}$在$c$内。
 
\begin{itemize}
   \item [1.] 
    对于情况一,可以删除$M_{n-1}$和$c$相交的三角形,删除的区域的边界是一条或者两条闭合曲线\footnote{删除区域是拓扑环带或者拓扑圆盘}，这些闭曲线和$c$形成拓扑环带，对这些拓扑环带进行网格剖分即完成n条闭合曲线的网格剖分。
    \item [2.]
    对于情况二，直接对$c$和$M_{n-1}$的边界形成的环带进行网格剖分即可。
\end{itemize}
故而问题归结于n边形的网格剖分和环带区域的网格剖分。




\begin{Definition}[凸点]
$n$欧式空间的n维闭流形$m$,$p$是$m$边界上的一点，$b_r$是以$p$为圆心$r$为半径的球，若当$r$足够小时，$b_r\bigcap m$是凸集合则称$p$是凸点。
否则称为非凸点。若$b_r\bigcap\left(R^n-m\right)$是凸集合，则称$p$是凹点。
\end{Definition}




\begin{Prop}
 对于多边形$c$,那么$c$上点必有一个凸点。
\end{Prop}
\begin{Proof}
反证法：假设全部是非凸点，也就是$c$上的角度全部朝向$c$的一侧，然后如果我们证明$c$的“内部区域”就是在$c$的这一侧，那么上述命题得证。

$c$上的角度全部朝向$c$的一侧，也就是$c$是凸多边形\footnote{用递推法}。凸多边形的内部区域自然是角度朝向的一侧\footnote{可以由凸边形的性质得到}。
\end{Proof}

如果把上述命题推广到n维光滑流形，证明涉及到全局微分和拓扑信息，还需要用到高斯曲率\cite{weifenjihe}等工具。


\begin{Prop}
命题2: 如果多边形$c$的角度全部朝向一侧，那么$c$是凸多边形。
\end{Prop}
\begin{Proof}
递推法：对三角形命题自然成立。

对于$n$边形可以看成$n-1$边形和一个三角形。
\end{Proof}

\begin{Prop}
多边形区域存在一个网格剖分。
\end{Prop}

\begin{Proof}
给定一个n边形$c_n$，那么存在一个对“内部区域”$U_n$的三角剖分。
\begin{itemize}
    \item[*]
     由命题一知道，$c_n$存在一个内角，那么这个内角可以构成一个三角形$s_n \in U_n$。那么$\left(U_n - s_n \right)\in U_n$,且构成一个新的多边形$c_{n-1}$
    \item[*]
    可知对于3边形，命题3成立，得证。
\end{itemize}
\end{Proof}


上述命题也可以推广:
\begin{Prop}
$n$维欧式空间存在一个$n-1$维不带边界闭流形$m$，那么存在以此流形为边界的网格剖分。
\end{Prop}
\begin{Proof}
证明同上也是构造性证明。
\begin{itemize}
    \item[*]
    找到一个凸点$p$,$m$上$p$点附近的区域$U$,$U$是带边$n-1$维流形。
    \item[*]
    对$U$进行拓扑网格剖分。
    \item[*]
    $m$所围区域减去$U$区域得到区域$C$。$C$的边界是$n-1$维闭流形$m_1$。再对$m_1$相同操作。

\end{itemize}
\end{Proof}

对于一每一角度，补一条线段，构成三角形。那么我们可以判断这条线段是否在多边形区域内部。
方法如下：对于任意直线$l$，它和多边形相交，这些角点构成多个线段，我们可以根据这些点的性质和线段顺序判断线段是否在多边形区域内部。
\begin{Definition}[有效交点]
若曲线$c$和直线$l$交于点$p$,且直线$l$不是$c$在$p$的承托超平面\textsuperscript{\cite{fanhanfen}}，那么称作$p$是有效交点。
\end{Definition}
我们可以把上述定义推广到二维流形或更高维流形。
\begin{Definition}[有效交点]
若$n$维欧式空间下$m$维流形$m$和直线$l$交于点$p$,且直线$l$在函数芽的等价条件下不是$p$的切空间元素，那么称作$p$是有效交点。

\end{Definition}



\begin{algorithm}
\caption{判断多边形上的点是否是凸点}
\label{is_inner}
\LinesNumbered
\KwIn{多边形$p_0,..p_n$,和其中的点$p_i$}
\KwOut{$p_i$上的点是否是凸点}
射线$p_{i-1},p_{i+1}$和多边形的有效交点为偶数，那么$p_i$上的角度是凸点。
\end{algorithm}
也可以按照定义进行判断，这样可以对任意维流形判断。
\begin{algorithm}
\caption{$n$维不带边界流形$m$上的点是否是凸点}
\label{is_inner}
\LinesNumbered
\KwIn{$n$维不带边界流形$m$上的点$p$}
\KwOut{$p$上的点是否是凸点}
对$p$在$m$上邻域的任意两点$p_1,p_2$,线段$p_1,p_2$在$m$所围区域的内部。则$p$是凸点。

关于判断$p_1,p_2$在$m$所围区域的内部参考如下命题。
\end{algorithm}


上述算法的依据是如下命题:
\begin{Prop}
若$n$维欧式空间的$n$维闭流形$m$上边界上的一点$p$，$l$是$p$为出发点的射线,若$l$在$p$邻域指向流形内部，则$l$与$m$的有效交点是偶数。
若$l$在$p$邻域指向流形外部，则$l$与$m$的有效交点是奇数。
\end{Prop}

\begin{Proof}
因为是闭流形，所以射线进入内部必然会出去。
\end{Proof}




\begin{Definition}[最小凸包]
设在向量空间$V$内有点集$p_i$,那么包含$p_i$的所有凸包的交称作$p_i$的最小凸包。
\end{Definition}

\begin{algorithm}
\caption{求多边形最小凸包}
\LinesNumbered
\KwIn{多边形$p_0,..p_n$}
\KwOut{最小凸包(凸多边形)}
    找出多变形的非凸点$p_i$。

    去除点$p_i$得到新的多边形$p_0..\hat{p_i}..p_n$。

    重复1。

\end{algorithm}

环带区域分割：只需切一刀，把环带切成多边形区域即可。

环带区域是亏格\cite{homotopy}为一的曲面，对于任意亏格曲面都可以通过“切一刀”使其变成单连通曲面。

\begin{algorithm}
\caption{求环带区域的切割线段}
\LinesNumbered
\KwIn{环带区域和它的边界$c_1$,$c_2$两条曲线}
\KwOut{切割环带的线段}
求$c_1$和$c_2$的最小凸包$\overline{c_1}$,$\overline{c_2}$。

取出$\overline{c_1}$的任意点p,再取出$\overline{c_2}$距离$p$最近顶点$q$。

线段$p,q$即为所求
\end{algorithm}

上述算法并不简洁，下面的叙述更加简洁而且更加普遍，对于高维的环带上述算法叙述为:


\begin{algorithm}
\caption{任意维环带的切割}
\LinesNumbered
\KwIn{环带区域和它的边界$c_1$,$c_2$两个边界}
\KwOut{切割环带}
选取$U_1\in c_1$和$U_2\in c_2$,满足$\forall p_1\in U_1$和$\forall p_2\in U_2$,线段$p_1,p_2$位于环带内部。

那么对$U_1\bigcup U_2$求凸包得到$C$,那么环带区域减去$C$,剩下的区域便是单连通流形。


\end{algorithm}








\begin{algorithm}
\caption{求多边形区域的网格剖分}
\LinesNumbered
\KwIn{多边形}
\KwOut{网格剖分}
    找出多变形的内角点$p_i$。

    得到三角形$p_{i-1},p_i,p_{i+1}$,并去除点$p_i$得到新的多边形$p_0..\hat{p_i}..p_n$。

    对多边形$p_0,..\hat{p_i}..p_n$重复1。
\end{algorithm}

\begin{algorithm}
\caption{求给定多条闭合曲线的网格剖分}
\LinesNumbered
\KwIn{$n$条闭合曲线}
\KwOut{网格剖分}
\label{poufen}
    当$n= 1$,也就是多边形区域的网格剖分。

    当$n> 1$,取出一条闭合曲线$c$,对剩下的$n-1$条闭合曲线进行网格剖分得到$M_{n-1}$。

    删除$c$和$M_{n-1}$相交的三角形，删除的区域有一条或者两条边界。这些边界和$c$形成拓扑环带，对这些环带区域进行网格剖分。


\end{algorithm}




对于任意维流形算法\ref{poufen}的叙述都是类似相同的。



\begin{center}
\begin{figure}[H]
\caption{煤堆和平面的相交曲线示意图1}
\end{figure}
\end{center}




\begin{figure}[H]
\centering
\subfigure[a]
{
\includegraphics[scale=0.1]{fenceng.png}
   
}
\subfigure[b]
{
\includegraphics[scale=0.1]{fenceng1.png}

}
\subfigure[c]
{
\includegraphics[scale=0.1]{fenceng2.png}
   
}

\caption{煤堆和平面的相交曲线}
\end{figure}

\begin{figure}[H]
\centering
\subfigure[a]
{
    \includegraphics[scale=0.1]{inter1.png}
}
\subfigure[b]
{
\includegraphics[scale=0.1]{inter3.png}
}
\subfigure[c]
{
   \includegraphics[scale=0.1]{inter2.png} 
}

\caption{普通曲面相交示意图}
\end{figure}






haskell语言编程会降低上述实现难度\cite{haskell},但是本文目前采用c/c++主要是因为目前c/c++生态较好。


\addcontentsline{toc}{chapter}{参考文献}
\bibliographystyle{plain}
\bibliography{intersection}

\clearpage
\addcontentsline{toc}{chapter}{附录}
\begin{center}
    \Large
    \textbf{附录}
\end{center}
本文程序主要使用的库有高维网格库libcell和可视化库viewer。
libcell地址\url{https://gitee.com/wujilingfeng/libcell}。
viewer地址\url{https://gitee.com/wujilingfeng/viewer}。



\end{document}
